package com.hy.prefix_add;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:前缀和
 * 前缀和（Prefix Sum）是一种常见的数学和计算机科学中的技术，用于计算数组或序列中某个范围内元素的和。前缀和可以帮助我们高效地回答各种与区间求和
 * 相关的问题，包括子数组和、子矩阵和、区间和等。
 *
 * 前缀和的基本思想是预先计算出数组的累积和，并将这些累积和存储在一个新的数组中，这个新数组就是前缀和数组。前缀和数组的第 i 个元素表示原始数组中
 * 前 i 个元素的累积和。
 *
 * 以下是前缀和的基本步骤：
 * 1、创建一个与原始数组大小相同的前缀和数组，初始值全部为0。
 * 2、从原始数组的第一个元素开始，依次计算累积和，并将每个累积和存储在前缀和数组中。
 * 3、前缀和数组的第 i 个元素等于原始数组前 i 个元素的和。
 * 4、通过前缀和数组，可以高效地回答区间和的查询。例如，要计算从原始数组的第l个元素到第r个元素的区间和，只需执行前缀和数组中第r个元素减去第l-1个元素即可。
 *
 * 应用领域包括但不限于：
 * 子数组和问题：查找数组中某个连续子数组的和。
 * 子矩阵和问题：在二维数组中查找某个子矩阵的和。
 * 区间和问题：计算数组中某个区间范围内元素的和，通常用于解决涉及统计和计算的问题。
 *
 * User:Mr.Du
 * Date:2023/9/26
 * Time:00:27
 */
public class PrefixAddTemplate {

    private int[] res;

    /* 查询闭区间 [left, right] 的累加和 */
    public PrefixAddTemplate(int[] nums) {
        res = new int[nums.length + 1];
        for(int i = 1;i < res.length;i++){
            // 计算 nums 的累加和
            res[i] = res[i - 1] + nums[i - 1];
        }
    }

    /* 查询闭区间 [left, right] 的累加和 */
    public int sumRange(int left, int right) {
        return res[right + 1] - res[left];
    }
}
